# OAEP (Optimal Asymmetric Encryption Padding)

## 1. 개요
**OAEP(Optimal Asymmetric Encryption Padding)**는 RSA와 같은 공개키 암호화 방식에서 평문을 암호화하기 전, 데이터의 무작위성을 부여하고 구조적 무결성을 확보하기 위해 사용하는 최적 비대칭 암호화 패딩 방식이다.

공개키 암호화 알고리즘인 RSA는 기본적으로 **결정론적 암호화(Deterministic Encryption)** 특성을 가진다. 즉, 동일한 공개키로 동일한 평문을 암호화하면 항상 동일한 암호문이 생성된다. 이는 공격자가 미리 계산된 표(Rainbow Table)를 이용하거나, 특정 메시지 여부를 추측하여 확인하는 선택 평문 공격(CPA)에 취약하게 만든다. OAEP는 평문에 무작위 값(Seed)을 결합하고 해시 함수를 통해 데이터를 변형함으로써, 동일한 평문이라도 암호화할 때마다 매번 다른 암호문이 생성되도록 하여 이러한 취약점을 해결한다.

## 2. MGF1 (Mask Generation Function 1)
OAEP의 핵심 메커니즘은 **MGF1(Mask Generation Function 1)**이라는 마스크 생성 함수에 의존한다. MGF1은 임의의 길이의 입력값을 받아, 사용자가 원하는 길이의 가변적인 출력값(마스크)을 생성하는 함수이다.

*   **역할:** 입력된 시드(Seed)나 데이터를 기반으로 의사 난수 스트림을 생성하여, XOR 연산을 통해 데이터를 은닉(Masking)하는 데 사용된다.
*   **동작 방식:** 내부적으로 SHA-256과 같은 해시 함수를 반복적으로 호출하며, 카운터(Counter) 값을 추가하여 매 반복마다 서로 다른 해시 결과값이 나오도록 설계되어 있다.
*   **특징:** 입력값이 조금만 변해도 출력값이 완전히 달라지는 확산(Diffusion) 특성을 가져, 데이터의 패턴을 완전히 제거한다.

## 3. 동작 원리 및 구조
OAEP는 평문을 직접 암호화하는 대신, 해시 함수와 MGF1을 이용한 두 단계의 마스킹 과정을 거쳐 패딩된 데이터를 생성한다.

### 3.1 암호화 패딩 흐름
1.  **데이터 준비:** 평문 $M$ 뒤에 구분자(Separator)인 `0x01` 바이트와 0으로 채워진 패딩 문자열인 **PS(Padding String)**를 추가하여 고정된 길이의 블록($DB$)을 만든다.
2.  **시드 생성:** 무작위 비트열인 시드($seed$)를 생성한다.
3.  **1차 마스킹:** $seed$를 MGF1에 입력하여 마스크를 생성하고, 이를 평문 블록과 XOR 연산한다. $\rightarrow$ $maskedDB$ 생성
4.  **2차 마스킹:** $maskedDB$를 다시 MGF1에 입력하여 마스크를 생성하고, 이를 $seed$와 XOR 연산한다. $\rightarrow$ $maskedSeed$ 생성
5.  **최종 결합:** $maskedSeed$와 $maskedDB$를 결합하여 최종 패딩 데이터($EM$)를 생성하고, 이를 RSA 알고리즘으로 암호화한다.

### 3.2 단계별 변환 과정
| 단계 | 입력값 | 처리 과정 | 결과값 | 비고 |
| :--- | :--- | :--- | :--- | :--- |
| **준비** | 평문 $M$, 레이블 $L$ | $L$의 해시값 + $M$ + `0x01` + $PS$ | $DB$ (Data Block) | 데이터 구조화 |
| **1차 마스킹** | $seed$, $DB$ | $DB \oplus \text{MGF1}(seed, \text{maskLen})$ | $maskedDB$ | 평문 은닉 |
| **2차 마스킹** | $maskedDB$, $seed$ | $seed \oplus \text{MGF1}(maskedDB, \text{seedLen})$ | $maskedSeed$ | 시드 은닉 |
| **최종** | $maskedSeed, maskedDB$ | 두 값의 결합 (Concatenation) | $EM$ (Encoded Message) | RSA 입력값 |

### 3.3 암호화 및 복호화 프로세스
```mermaid
graph TD
    subgraph Encryption
    A[Plaintext M] --> B[Add Label Hash & PS]
    B --> C[DB]
    D[Random Seed] --> E[MGF1]
    E --> F[XOR with DB]
    F --> G[maskedDB]
    G --> H[MGF1]
    H --> I[XOR with Seed]
    I --> J[maskedSeed]
    J --> K[Concatenate: EM]
    K --> L[RSA Encryption]
    L --> M[Ciphertext]
    end

    subgraph Decryption
    M --> N[RSA Decryption]
    N --> K2[EM]
    K2 --> O[Split: maskedSeed & maskedDB]
    O --> P[MGF1 with maskedDB]
    P --> Q[XOR with maskedSeed]
    Q --> R[Seed]
    R --> S[MGF1 with Seed]
    S --> T[XOR with maskedDB]
    T --> U[DB]
    U --> V[Integrity Check & Extract M]
    V --> W[Plaintext M]
    end
```

## 4. 주요 특징 및 보안성
### 4.1 CCA2 저항성
OAEP는 **적응적 선택 암호문 공격(Adaptive Chosen Ciphertext Attack, CCA2)**에 대해 강력한 저항성을 가진다. CCA2는 공격자가 임의의 암호문을 생성해 복호화 오라클(Oracle)에 요청하고 그 결과를 통해 개인키나 평문을 유추하는 공격이다. 

OAEP는 복호화 과정에서 패딩 구조의 무결성을 엄격히 검사한다. 이때 보안을 위해 오류 발생 시 공격자가 오류의 원인을 구분할 수 없도록 동일한 일반 오류 메시지를 반환하거나, 일정한 시간을 소요하게 하는 **상수 시간(Constant-time)** 구현을 적용하여 내부 정보가 누설되지 않도록 설계되었다.

### 4.2 무작위성 (Randomness)
무작위 시드($seed$)를 사용함으로써 **확률적 암호화(Probabilistic Encryption)**를 구현한다. 이는 동일한 평문을 여러 번 암호화하더라도 매번 다른 암호문이 생성되게 하여, 공격자가 암호문만 보고 평문의 내용을 추측하는 것을 방지한다.

## 5. PKCS#1 v2.1 표준 및 구현
OAEP는 RSA 암호화 표준인 **PKCS#1 v2.1** (및 이후 버전)에서 정의되어 있으며, 현대적인 RSA 구현의 기본 패딩 방식으로 권장된다.

### 5.1 세부 제약 사항
표준에 따라 OAEP를 구현할 때 다음과 같은 제약 사항을 준수해야 한다.
*   **최대 평문 길이:** 암호화 가능한 최대 평문 길이는 $k - 2h - 2$ 바이트이다. (여기서 $k$는 RSA 모듈러스의 바이트 길이, $h$는 사용된 해시 함수의 출력 바이트 길이)
*   **해시 함수 일관성:** MGF1에서 사용하는 해시 함수와 OAEP의 레이블 해싱에 사용하는 해시 함수는 동일해야 한다.
*   **시드 길이:** 시드의 길이는 사용되는 해시 함수의 출력 길이($h$)와 동일하게 설정해야 한다.

### 5.2 Python 구현 예시 (`cryptography` 라이브러리)
```python
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import rsa, padding

# 1. RSA 키 쌍 생성
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

message = b"Hello, OAEP Wiki!"

# 2. OAEP 패딩을 이용한 암호화
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None # 레이블은 선택 사항
    )
)

# 3. OAEP 패딩을 이용한 복호화
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(f"Decrypted: {plaintext.decode()}")
```

## 6. 다른 패딩 방식과의 비교 및 취약점
### 6.1 PKCS#1 v1.5 vs OAEP
과거에 널리 쓰인 PKCS#1 v1.5는 단순한 구조로 인해 심각한 보안 취약점이 발견되었다.

| 비교 항목 | PKCS#1 v1.5 | OAEP |
| :--- | :--- | :--- |
| **구조** | 단순 패딩 (Random bytes + 00) | 해시 기반 마스킹 (Feistel-like) |
| **암호화 특성** | 결정론적 성향 강함 | 완전한 확률적 암호화 |
| **보안성** | CCA 공격에 취약 | CCA2 저항성 보유 |
| **검증 과정** | 단순 구조 확인 | 해시 및 패딩 무결성 엄격 검증 |
| **성능** | 매우 빠름 | 해시 연산으로 인해 약간 느림 |

### 6.2 패딩 오류를 이용한 공격 (Bleichenbacher's Attack)
PKCS#1 v1.5의 가장 대표적인 취약점은 **블라이헨바허 공격(Bleichenbacher's Attack)**이다. 이 공격은 복호화 과정에서 패딩이 잘못되었을 때 서버가 반환하는 **오류 메시지의 차이(Padding Oracle)**를 이용한다.

*   **공격 원리:** 공격자가 암호문을 미세하게 변조하여 전송했을 때, 서버가 "패딩 오류"인지 "복호화 성공 후 데이터 오류"인지를 다르게 응답한다면, 공격자는 이 응답 차이를 통해 평문의 비트 정보를 하나씩 알아낼 수 있다.
*   **OAEP의 대응:** OAEP는 v1.5에 비해 구조적으로 훨씬 강력한 방어 체계를 갖추고 있다. 비록 최근 OAEP 기반의 Manger's attack과 같은 정교한 공격 기법이 제안되기도 하였으나, 엄격한 무결성 검사와 상수 시간 응답 설계를 통해 오라클 공격의 난이도를 극도로 높여 실질적으로 방어하도록 설계되었다.